package com.example.leetcode.prcatice;

import java.util.ArrayList;
import java.util.List;

/**
 * 给定一个单链表 L 的头节点 head ，单链表 L 表示为：
 *
 * <p> L0 → L1 → … → Ln-1 → Ln  请将其重新排列后变为：
 *
 * <p>L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …
 *
 * <p>来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/LGjMqU 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class OfferII26 {

    public void reorderList(ListNode head) {
        if (head == null){
            return;
        }
        ListNode pre = head;
        List<ListNode> list = new ArrayList<>();
        while (pre != null){
            list.add(pre);
            pre = pre.next;
        }
        int size = list.size();
        ListNode newHead = new ListNode();
        ListNode tail = newHead;
        int left = 0,right = size-1;
        ListNode nodeLeft;
        ListNode nodeRight;
        while (left <= right){
           if (left != right){
               tail.next = list.get(left);
               nodeRight = list.get(right);
               tail.next.next = nodeRight;
               tail = nodeRight;
           }else {
               nodeLeft = list.get(left);
               tail.next = nodeLeft;
               tail = nodeLeft;
           }
           left++;
           right--;
        }
        tail.next = null;
        head = newHead.next;
        while (head != null){
            System.out.println("val="+head.val);
            head = head.next;
        }
    }
}


class DemoOfferII26{
  public static void main(String[] args) {
      ListNode head = new ListNode(1);
      head.next = new ListNode(2);
      head.next.next = new ListNode(3);
      head.next.next.next = new ListNode(4);
      head.next.next.next.next = new ListNode(5);
      OfferII26 o = new OfferII26();
      o.reorderList(head);
  }
}
